import java.util.*;

public class demo1 {
    /**
     * 763.划分字母区间
     * https://leetcode.cn/problems/partition-labels/submissions/630280055/
     */
    public List<Integer> partitionLabels(String s) {
        // 1.遍历整个字符串，记录每个字符出现的最后下标
        char[] ss = s.toCharArray();
        int[] last = new int[26];
        int n = s.length();
        for(int i = 0;i < n;i++) {
            // 记录每个字符在数组中出现的最后位置
            last[ss[i] - 'a'] = i;
        }
        // 2.再次遍历ss，进行统计片段
        List<Integer> ret = new ArrayList<>();
        int start = 0,end = 0; // 记录每个片段出现的开始和结束位置
        for(int i = 0;i < n;i++) {
            end = Math.max(end,last[ss[i] - 'a']); // end为每个片段中出现的最后一个单词的位置
            // 当end 和 下标 i 相等的时候，说明这个片段就结束了，就需要统计
            // 比如：ababcbacadefegdehijhklij
            // end为8，因为 ababcbaca 这个片段的最大值的位置为a的位置8
            if(end == i) {
                ret.add(end - start + 1);
                start = end + 1;
            }
        }
        return ret;
    }
}
